package com.kevin.Code.LinkNode;

/**
 * @author Vinlee Xiao
 * @Classname ReverseKNode
 * @Description Leetcode 25. K 个一组翻转链表 二刷 明确难点 困难
 * @Date 2022/3/31 11:09
 * @Version 1.0
 */
public class ReversekNode {

    /**
     * 理清思路是关键
     * 难点:细节
     *
     * @param head 头结点
     * @param k    k组
     * @return 返回反转链表后的头结点
     */
    public ListNode reverseKGroup(ListNode head, int k) {

        if (k == 1) {
            return head;
        }

        //辅助结点哑结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //没k个链表的尾结点
        ListNode tail = dummy;
        //用于每次记录每轮k个结点的头结点
        ListNode pre = dummy;


        while (head != null) {
            //找到k组结点的尾结点
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                //说不不足k个结点,直接返回头结点
                if (tail == null) {
                    return dummy.next;
                }
            }
            //尾结点的下一个结点
            ListNode nex = tail.next;
            ListNode[] listNode = reverseNode(head, tail);
            head = listNode[0];
            tail = listNode[1];

            pre.next = head;
            tail.next = nex;
            pre = tail;
            head = tail.next;
        }

        return dummy.next;
    }


    /**
     * 思路反转链表，关键要找到尾结点的后驱结点
     *
     * @param head 头结点
     * @param tail 尾结点 tail保证不为null
     * @return 返回反转后链表的头结点和尾结点
     */
    private ListNode[] reverseNode(ListNode head, ListNode tail) {
        ListNode pre = tail.next;
        //移动结点
        ListNode move = head;

        while (pre != tail) {
            ListNode nextNode = move.next;
            move.next = pre;
            pre = move;
            move = nextNode;
        }

        //最终的结果是原来的头结点变成尾结点，尾结点变成头结点
        return new ListNode[]{tail, head};
    }
}
